package com.lipp.luosu.avl;

import lombok.extern.slf4j.Slf4j;

/**
 * @ClassName AVLTree
 * @description: TODO 类描述
 * @Author lipp
 * @Date 2024/1/22 9:22
 * @Version 1.0
 */
@Slf4j
public class AVLTree {
    /**
     * @description: 根节点
     */
    volatile Node root;

    /**
     * @param node
     * @return
     * @description: 获取节点高度
     */
    public int height(Node node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    public int max(int a, int b) {
        return a > b ? a : b;
    }

    /**
     * 右旋
     *
     * @param y 发现节点
     * @return 发现节点的左儿子 --> 发现节点
     * @description: 发现节点的左儿子成为他爸爸，自己降级为右孩子；发现节点的左儿子的右孩子 成为原来的左儿子
     */
    private Node rightRotate(Node y) {
        // todo 初始
        // x是y的左孩子，T2是x的右孩子
        Node x = y.left;
        Node T2 = x.right;

        // 发现节点的儿子成爸爸
        x.right = y;
        // 发现节点的孙子成儿子
        y.left = T2;


        // 父节点的度 = 左右孩子最大度 + 1
        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        // 返回新的根结点
        return x;
    }

    /**
     * @param y 发现节点
     * @return 发现节点的右孩子 --> 发现节点
     * @todo 左旋
     * @description: 发现节点的右孩子成为他父亲，自己降级为左孩子；发现节点的右孩子的左孩子 成为原来的右孩子
     */
    private Node leftRotate(Node y) {
        // 发现结点的右孩子
        Node x = y.right;
        // 发现结点的右孩子的左孙子
        Node T2 = x.left;

        y.right = T2;
        x.left = y;
        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;
        return x;
    }


    /**
     * 节点平衡因子 = 左子树的度 - 右子树的度
     *
     * @param node
     * @return
     * @description: 获取节点平衡度
     */
    private int getBalance(Node node) {
        return node == null ? 0 : height(node.left) - height(node.right);
    }

    /**
     * 平衡二叉树插入
     *
     * @param node 根节点
     * @param key
     * @return 一颗完整的树
     */

    synchronized Node insert(Node node, int key) {
        // 1.建立一个值为key的新节点
        if (node == null) {
            return new Node(key);
        }
        // 1.遍历插入的时候，左、右孩子为空，赋值返回。这边是递归搜索，找到有空的地方插入，然后在那一层开始判断是否有发现节点
        if (key < node.key) {
            // 左子树插入
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            // 右子树插入
            node.right = insert(node.right, key);
        } else {
            // 重复插入
            return node;
        }
        // 更新祖先节点的高度
        node.height = max(height(node.left), height(node.right)) + 1;
        // 检查节点的平衡因子
        int balance = getBalance(node);
        // 找谁是第一个发现节点
        if (balance > 1 && key < node.left.key) {
            log.info("破坏节点 {} 在发现节点 {} 左孩子的左子树，满足LL,需要右旋！ ", key, node.key);
            // 右旋
            return rightRotate(node);
        }
        if (balance < -1 && key > node.right.key) {
            log.info("破坏节点 {} 在发现节点 {} 右孩子的右子树，满足RR,需要左旋！ ", key, node.key);
            // 左旋
            return leftRotate(node);
        }
        if (balance > 1 && key > node.left.key) {
            // LR 先左后右
            log.info("破坏节点 {} 在发现节点 {} 左孩子{}的右子树，满足LR,需要左孩子{}作为核心完成左旋，然后发现节点{}再右旋！ ", key, node.key, node.left.key, node.left.key, node.key);
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        if (balance < -1 && key < node.right.key) {
            // RL 先右后左
            log.info("破坏节点 {} 在发现节点 {} 右孩子{}的左子树，满足RL,需要右孩子{}作为核心完成右旋，然后发现节点{}再左旋！ ", key, node.key, node.right.key, node.right.key, node.key);
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

    public Node delete(Node node, int key) {
        if (node == null) {
            return null;
        }
        // todo 第一步：先删除掉结点
        // 左子树递归查找删除
        if (key < node.key) {
            node.left = delete(node.left, key);
        }
        // 右子树递归查找删除
        else if (key > node.key) {
            node.right = delete(node.right, key);
        }
        // 找到了要删除的结点
        else {
            // 1.没有左孩子，右孩子 直接删除该结点
            if (node.left == null && node.right == null) {
                return null;
            }
            // 2.只有右孩子，右子树补上
            else if (node.left == null && node.right != null) {
                return node.right;
            }
            // 3.只有左孩子，左子树补上
            else if (node.left != null && node.right == null) {
                return node.left;
            }
            // 4.左、右孩子都有
            else {
                // todo 这边采取互换，互换有两种方式。一个是跟右子树的最小结点互换，一个是跟左子树最大互换，互换后再删除，这个随意选择，作者在这选择第一种。
                Node min = findMinInRight(node.right);
                log.info("插入节点是 {},跟他转换的右子树最小节点是{}",node.key,min.key);
                // 倒反天罡
                node.key = min.key;
                // todo 已经互换了，所以要将原节点递归查找删除,从替换的节点回溯到原节点的位置，会开始检测是否存在不平衡现象
                node.right = delete(node.right, min.key);
            }
        }
        node.height = max(height(node.left), height(node.right)) + 1;
        int balance = getBalance(node);
        //todo 删完后，开始平衡操作
        if (balance > 1) {
            StringBuilder sb1 = new StringBuilder();
            if (getBalance(node.left) < 0) {
                sb1.append(String.format("破坏节点在发现节点%d的左孩子%d的右子树，需要先将左孩子%d作为根节点左旋，再", node.key, node.left.key, node.left.key));
                node.left = leftRotate(node.left);
            }
            sb1.append(String.format("发现节点%d右旋", node.key));
            log.info(sb1.toString());
            node = rightRotate(node);
        } else if (balance < -1) {
            StringBuilder sb2 = new StringBuilder();
            if (getBalance(node.right) > 0) {
                sb2.append(String.format("破坏节点在发现节点%d的右孩子%d的左子树，需要先将右孩子%d作为根节点右旋，再", node.key, node.right.key, node.right.key));
                node.right = rightRotate(node.right);
            }
            sb2.append(String.format("发现节点%d左旋", node.key));
            log.info(sb2.toString());
            node = leftRotate(node);
        }

        return node;
    }

    /**
     * 寻找最小结点
     *
     * @param node
     * @return 其实这个结点只有右孩子
     */
    private Node findMinInRight(Node node) {
        if (node.left == null) {
            return node;
        }
        return findMinInRight(node.left);
    }

}
